package leetcode.L239;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    //滑动窗口最大值
    public static int[] maxSlidingWindow(int[] nums, int k) {

        if (nums.length < k) return null;

        int[] ans = new int[nums.length - k+1];

        //0是位置，1是数字，position越前的越先出
        PriorityQueue<int[]> queue = new PriorityQueue<>(
                new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return o1[1] == o2[1] ? o2[0] - o1[0] : o2[1] - o1[1];
                    }
                }
        );

        for (int i = 0; i < k; i++) {
            int[] currArr = new int[]{i, nums[i]};
            queue.add(currArr);
        }
        assert queue.peek() != null;
        ans[0] = queue.peek()[1];

        int index = k;
        while (index < nums.length) {
            //先添加
            queue.add(new int[]{index, nums[index]});

            while (queue.peek()[0] <= index - k) {
                queue.poll();
            }
            int[] currentMax = queue.peek();
            ans[index - k + 1] = currentMax[1];
            index++;
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        System.out.println(Arrays.toString(arr));
    }
}